package fun.ticsmyc.dataStructure;

/**
 * 01字典树
 * 主要解决 求异或最值问题
 * @author Ticsmyc
 * @date 2021-03-30 11:28
 */
public class ZeroOneTrie {

    Node root = new Node();

    /**
     * 按二进制从高到低插入
     * @param num
     */
    public void insert(int num){
        Node cur = root;
        for (int i = 31; i >= 0; --i) {
            int op = ((num >> i) & 1);
            if(cur.next[op] == null) {
                cur.next[op] = new Node();
            }
            cur = cur.next[op];
            cur.count++;
        }
        cur.val = num;
    }

    /**
     * 从字典树上删除一个值
     * （要确保这个值存在）
     *
     * @param num
     */
    public void delete(int num) {
        Node cur = root;
        for (int i = 31; i >= 0; --i) {
            int op = ((num >> i) & 1);
            if(cur.next[op].count == 1) {
                cur.next[op] = null;
                return;
            } else {
                cur = cur.next[op];
                cur.count--;
            }
        }
    }

    /**
     * 查询所有数中和num异或结果最大的数
     *
     * @return
     */
    public int queryMax(int num) {
        Node cur = root;
        for (int i = 31; i >= 0; --i) {
            int op = ((num >> i) & 1) == 0 ? 1 : 0;
            if(cur.next[op] != null) {
                cur = cur.next[op];
            } else {
                op = op ^ 1;
                cur = cur.next[op];
            }
        }
        return cur.val;
    }

    public int queryMin(int num){
        Node cur = root;
        for(int i=31;i>=0;--i){
            int op =((num>>i)&1);
            if(cur.next[op]!=null){
                cur=cur.next[op];
            }else{
                cur=cur.next[op^1];
            }
        }
        return cur.val;
    }

    private class Node{
        public int count =0;
        public int val =0;
        public Node[] next =new Node[2];
    }
}
